Elastic partitioning of computations between mobile devices and cloud is an important and challenging research topic for mobile cloud computing. Existing works focus on the single-user computation partitioning, which aims to optimize the application completion time for one particular single user. These works assume that the cloud always has enough resources to execute the computations immediately when they are offloaded to the cloud. However, this assumption does not hold for large scale mobile cloud applications. In these applications, due to the competition for cloud resources among a large number of users, the offloaded computations may be executed with certain scheduling delay on the cloud. Single user partitioning that\uddoes not take into account the scheduling delay on the cloud may yield significant performance degradation. In this paper, we study, for the first time, Multi-user Computation Partitioning Problem (MCPP), which considers the partitioning of multiple users’ computations together with the scheduling of offloaded computations on the cloud resources. Instead of pursuing the minimum application completion time for every single user, we aim to achieve minimum average completion time for all the users, based on\udthe number of provisioned resources on the cloud. We show that MCPP is different from and more difficult than the classical job scheduling problems. We design an offline heuristic algorithm, namely SearchAdjust, to solve MCPP. We demonstrate through benchmarks that SearchAdjust outperforms both the single user partitioning approaches and classical job scheduling approaches by 10% on average in terms of application delay. Based on SearchAdjust, we also design an online algorithm for MCPP that can be easily deployed in practical systems. We validate the effectiveness of our online algorithm using real world load traces.\ud\udIndex Terms—mobile cloud computing; offloading; computation partitioning; job scheduling
展开▼
机译：移动设备和云之间的计算弹性分区是移动云计算的重要且具有挑战性的研究主题。现有工作集中在单用户计算分区上，该分区旨在为一个特定的单用户优化应用程序完成时间。这些工作假定云始终有足够的资源在将计算卸载到云时立即执行计算。但是，该假设不适用于大规模移动云应用程序。在这些应用中，由于大量用户之间对云资源的竞争，可以在云上以一定的调度延迟执行卸载的计算。不考虑云上的调度延迟的单用户分区可能会导致性能显着下降。在本文中，我们首次研究了多用户计算分区问题（MCPP），该问题考虑了多用户计算的分区以及云资源上卸载计算的调度。我们的目标不是基于每个用户的最短应用完成时间，而是基于云上已调配资源的数量，为所有用户实现最短的平均完成时间。我们表明，MCPP与传统的作业调度问题不同，并且难度更大。我们设计了一种离线启发式算法SearchAdjust来解决MCPP。我们通过基准测试表明，就应用程序延迟而言，SearchAdjust的性能平均比单用户分区方法和传统作业计划方法均高10％。基于SearchAdjust，我们还为MCPP设计了一种在线算法，可以很容易地在实际系统中部署该算法。我们使用真实世界的负载跟踪来验证在线算法的有效性。\ ud \ udIndex术语-移动云计算；卸载计算分区；工作安排
展开▼
